package 简单.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，
 * 如果两者相等，返回 true 。# 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/backspace-string-compare
 */
public class 比较含退格的字符串_844 {

    public static void main(String[] args) {

    }

    /**
     * 栈+预处理
     */
    public boolean backspaceCompare(String s, String t) {
        Deque<Character> sStack = new ArrayDeque<>();
        Deque<Character> tStack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '#') {
                sStack.pollFirst();
            } else {
                sStack.addFirst(c);
            }
        }
        for (char c : t.toCharArray()) {
            if (c == '#') {
                tStack.pollFirst();
            } else {
                tStack.addFirst(c);
            }
        }

        if (sStack.size() != tStack.size()) return false;

        while (!sStack.isEmpty()) {
            if (sStack.pollFirst() != tStack.pollFirst()) {
                return false;
            }
        }
        return true;
    }

}
